{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #传递信息"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #传递信息"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0</li>\n",
    "\t<li>每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。</li>\n",
    "\t<li>每轮信息必须需要传递给另一个人，且信息可重复经过同一个人</li>\n",
    "</ol>\n",
    "\n",
    "<p>给定总玩家数 <code>n</code>，以及按 <code>[玩家编号,对应可传递玩家编号]</code> 关系组成的二维数组 <code>relation</code>。返回信息从小 A (编号 0 ) 经过 <code>k</code> 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3</code></p>\n",
    "\n",
    "<p>输出：<code>3</code></p>\n",
    "\n",
    "<p>解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0-&gt;2-&gt;0-&gt;4， 0-&gt;2-&gt;1-&gt;4， 0-&gt;2-&gt;3-&gt;4。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>n = 3, relation = [[0,2],[2,1]], k = 2</code></p>\n",
    "\n",
    "<p>输出：<code>0</code></p>\n",
    "\n",
    "<p>解释：信息不能从小 A 处经过 2 轮传递到编号 2</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 5</code></li>\n",
    "\t<li><code>1 &lt;= relation.length &lt;= 90, 且 relation[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= relation[i][0],relation[i][1] &lt; n 且 relation[i][0] != relation[i][1]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [chuan-di-xin-xi](https://leetcode.cn/problems/chuan-di-xin-xi/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [chuan-di-xin-xi](https://leetcode.cn/problems/chuan-di-xin-xi/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]]\\n3', '3\\n[[0,2],[2,1]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dp = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(k):\n",
    "            for edge in relation:\n",
    "                src=edge[0]\n",
    "                tgt=edge[1]\n",
    "                dp[i+1][tgt]+=dp[i][src]\n",
    "        return dp[k][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        self.ways, self.n, self.k = 0, n, k\n",
    "        self.edges = collections.defaultdict(list)\n",
    "        for src, dst in relation:\n",
    "            self.edges[src].append(dst)\n",
    "\n",
    "        self.dfs(0,0)\n",
    "        return self.ways \n",
    "\n",
    "    def dfs(self, index, steps):\n",
    "        if steps == self.k:\n",
    "            if index == self.n-1:\n",
    "                self.ways += 1\n",
    "            return\n",
    "        for to in self.edges[index]:\n",
    "            self.dfs(to, steps+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dp = [[0 for _ in range(n)] for _ in range(k+1)]\n",
    "        dp[0][0] = 1\n",
    "        print(dp)\n",
    "        for l in range(k):\n",
    "            for x,y in relation:\n",
    "                dp[l+1][y] += dp[l][x] \n",
    "\n",
    "        return dp[k][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        '''\n",
    "        #  BFS\n",
    "        #重要操作，defaultlist,defaultlist.append()\n",
    "        edges=collections.defaultdict(list)\n",
    "        for edge in relation:\n",
    "            src=edge[0]\n",
    "            dst=edge[1]\n",
    "            edges[src].append(dst)\n",
    "        steps=0\n",
    "        queue=collections.deque([0])\n",
    "        while queue and steps<k:\n",
    "            steps+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                index=queue.popleft()\n",
    "                to=edges[index]\n",
    "                for nextIndex in to:\n",
    "                    queue.append(nextIndex)\n",
    "        ways=0\n",
    "        if steps==k:\n",
    "            while queue:\n",
    "                if queue.popleft()==n-1:\n",
    "                    ways+=1\n",
    "        return ways\n",
    "        '''\n",
    "        dp=[[0 for _ in range(n+1)]  for _ in range(k+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(k):\n",
    "            for edge in relation:\n",
    "                src=edge[0]\n",
    "                dst=edge[1]\n",
    "                dp[i+1][dst]+=dp[i][src]\n",
    "        return dp[k][n-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        # self.way记录个数， self.n记录节点数， self.k记录步骤数\n",
    "        self.ways , self.n , self.k = 0 , n , k\n",
    "        # 初始化节点对应的边\n",
    "        self.edge = collections.defaultdict(list)\n",
    "        # 将relation的数据转化为节点-边的字典\n",
    "        for node , linkNode in relation:\n",
    "            self.edge[node].append(linkNode)\n",
    "        # 从节点0，第0步开始调用深度遍历\n",
    "        self.dfs(0 , 0)\n",
    "        # 返回self.way记录数\n",
    "        return self.ways\n",
    "    \n",
    "    def dfs(self , index , steps):\n",
    "        # 结束条件是到达最大步数并且索引指向最后一个数\n",
    "        if steps == self.k:\n",
    "            if index == self.n - 1:\n",
    "                self.ways += 1\n",
    "            return\n",
    "        # 单层遍历节点所有的边\n",
    "        for i in self.edge[index]:\n",
    "            self.dfs(i , steps + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: list[int], k: int) -> int:\n",
    "        self.ways = 0\n",
    "        self.n = n\n",
    "        self.k = k\n",
    "        self.edges = collections.defaultdict(list)\n",
    "        for src, dst in relation:\n",
    "            self.edges[src].append(dst)\n",
    "\n",
    "        self.dfs(0, 0)\n",
    "        return self.ways\n",
    "\n",
    "    def dfs(self, index, steps):\n",
    "        if steps == self.k:\n",
    "            if index == self.n - 1:\n",
    "                self.ways += 1\n",
    "            return\n",
    "        for to in self.edges[index]:\n",
    "            self.dfs(to, steps + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "      \n",
    "        dp=[[0]*n for _ in range(k+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(k+1):\n",
    "            for x, y in relation:\n",
    "                dp[i][y]+=dp[i-1][x]\n",
    "        return dp[k][n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        f = []\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        for step in range(k):\n",
    "            nx = [0] * n\n",
    "            for i,j in relation:\n",
    "                if f[i]:\n",
    "                    nx[j] += f[i]\n",
    "            f = nx  \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        self.ways,self.n,self.k=0,n,k\n",
    "        self.edges=collections.defaultdict(list)\n",
    "        #将嵌套的数组利用字典构建成图的结构\n",
    "        for src,dst in relation:\n",
    "            self.edges[src].append(dst)\n",
    "        \n",
    "        self.dfs(0,0)\n",
    "        return self.ways\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, index, steps):#这种采用了深度优先搜索\n",
    "            if steps == self.k:\n",
    "                if index == self.n-1:\n",
    "                    self.ways += 1\n",
    "                return\n",
    "            for to in self.edges[index]:\n",
    "                self.dfs(to, steps+1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(k):\n",
    "            next = [0 for _ in range(n + 1)]\n",
    "            for edge in relation:\n",
    "                src = edge[0]\n",
    "                dst = edge[1]\n",
    "                next[dst] += dp[src]\n",
    "            dp = next\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        relation_map = [[] for _ in range(n)]\n",
    "        for r in relation:\n",
    "            relation_map[r[0]].append(r[1])\n",
    "\n",
    "        result = [[0] * n for _ in range(2)]\n",
    "        result[0][0] = 1\n",
    "        nodes = [0]\n",
    "        for epoch in range(1, k+1):\n",
    "            result[epoch%2] = [0] * n\n",
    "            new_nodes = []\n",
    "            for node in nodes:\n",
    "                connect = relation_map[node]\n",
    "                for c in connect:\n",
    "                    result[epoch%2][c] += result[(epoch-1)%2][node]\n",
    "                new_nodes.extend(connect)\n",
    "            nodes = list(set(new_nodes))\n",
    "        \n",
    "        return result[k%2][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        self.ways , self.n , self.k = 0 , n , k\n",
    "        self.edge = collections.defaultdict(list)\n",
    "        for node , link in relation:\n",
    "            self.edge[node].append(link)\n",
    "        self.dfs(0 , 0)\n",
    "        return self.ways\n",
    "    \n",
    "    def dfs(self , index , steps):\n",
    "        if steps == self.k:\n",
    "            if index == self.n - 1:\n",
    "                self.ways += 1\n",
    "            return\n",
    "        for to in self.edge[index]:\n",
    "            self.dfs(to , steps + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        adjvex = {}\n",
    "        for i in range(n):\n",
    "            adjvex[i] = []\n",
    "        for x, y in relation:\n",
    "            adjvex[x].append(y)\n",
    "\n",
    "        dis = [[0] * n for _ in range(n)]\n",
    "        for x, y in relation:\n",
    "            dis[x][y] = 1\n",
    "        \n",
    "        # 深度优先遍历，满足两个条件，0-4有路且dis=3\n",
    "        self.res = 0\n",
    "        print(adjvex)\n",
    "        def dfs(x, step):\n",
    "            if step==k:\n",
    "                if x==n-1:\n",
    "                    self.res += 1\n",
    "                return\n",
    "            for y in adjvex[x]:\n",
    "                dfs(y, step+1)\n",
    "        dfs (0, 0)\n",
    "        return self.res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        arr = [0]*n\n",
    "        arr[0] = 1\n",
    "        for i in range(k):\n",
    "            temp = [0]*n\n",
    "            for j in relation:\n",
    "                temp[j[1]]+=arr[j[0]]\n",
    "            arr = temp.copy()\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        arr = [0]*n\n",
    "        arr[0] = 1\n",
    "        for i in range(k):\n",
    "            temp = [0]*n\n",
    "            for j in relation:\n",
    "                temp[j[1]]+=arr[j[0]]\n",
    "            arr = temp\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        adj = collections.defaultdict(set)\n",
    "        for x, y in relation:\n",
    "            adj[x].add(y)\n",
    "\n",
    "        def dfs(x:int, step: int) -> None:\n",
    "            if step == k:\n",
    "                if x == n-1:\n",
    "                    self.res += 1\n",
    "                return\n",
    "            for y in adj[x]:\n",
    "                dfs(y, step + 1)\n",
    "\n",
    "        self.res = 0\n",
    "        dfs(0,0)\n",
    "        return self.res                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        def dfs(i, step, ans):\n",
    "            # print(i, step, ans)\n",
    "            if step >k: return ans\n",
    "            for ix in g[i]:\n",
    "                if ix == n-1 and step ==k-1:\n",
    "                    ans += 1\n",
    "                    # return ans\n",
    "                if ix!=n-1 and not g[ix]:\n",
    "                    continue\n",
    "                \n",
    "                ans = dfs(ix, step+1, ans)\n",
    "                \n",
    "            return ans\n",
    "                \n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in relation:\n",
    "            g[u].append(v)\n",
    "        # print(g)\n",
    "        # ans = 0\n",
    "        ans = dfs(0,0,0)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        grap=[[]for i in range(n)]\n",
    "        for x,y in relation:\n",
    "            grap[x].append(y)\n",
    "        def f(x,target,ct):\n",
    "            nex=grap[x]\n",
    "            if ct==k:\n",
    "                if x==target:\n",
    "                    nonlocal ans\n",
    "                    ans+=1 \n",
    "                return \n",
    "    \n",
    "            for p in nex:\n",
    "                f(p,target,ct+1)\n",
    "        ans=0\n",
    "        f(0,n-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        adjvex = collections.defaultdict(set)\n",
    "        for x, y in relation:\n",
    "            adjvex[x].add(y)\n",
    "        \n",
    "        def dfs(x: int, step: int):\n",
    "            if step == k:\n",
    "                if x == n - 1:\n",
    "                    self.res += 1\n",
    "                return\n",
    "            for y in adjvex[x]:\n",
    "                dfs(y, step + 1)\n",
    "        self.res = 0\n",
    "        dfs(0, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "\n",
    "        adj = collections.defaultdict(set)\n",
    "\n",
    "        for x, y in relation:\n",
    "            adj[x].add(y)\n",
    "\n",
    "        def dfs(x,step):\n",
    "            if step == k:\n",
    "                if x == n-1:\n",
    "                    self.res += 1\n",
    "                return \n",
    "            for y in adj[x]:\n",
    "                dfs(y,step+1)\n",
    "        self.res = 0\n",
    "        dfs(0,0)\n",
    "        return self.res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        rela_dict = defaultdict(list)\n",
    "        for i, (in_, out_) in enumerate(relation):\n",
    "            rela_dict[in_].append(out_)\n",
    "        print(rela_dict)\n",
    "\n",
    "        res = 0\n",
    "        def dfs(idx, step):\n",
    "            nonlocal res, n\n",
    "            print(idx, step)\n",
    "            if step == 0 and idx == n - 1:\n",
    "                res += 1\n",
    "                return\n",
    "            if not rela_dict[idx] or step == 0:\n",
    "                return\n",
    "            for child in rela_dict[idx]:\n",
    "                dfs(child, step - 1)\n",
    "        \n",
    "        dfs(0, k)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        adjvex = collections.defaultdict(set)\n",
    "        for x, y in relation:\n",
    "            adjvex[x].add(y)\n",
    "\n",
    "        Q = collections.deque()\n",
    "        Q.append(0)\n",
    "        step = 0\n",
    "        while Q and step < k :\n",
    "            cur_len = len(Q)\n",
    "            for _ in range(cur_len):\n",
    "                x = Q.popleft()\n",
    "                for y in adjvex[x]:\n",
    "                    Q.append(y)\n",
    "            step += 1\n",
    "        \n",
    "        res = 0\n",
    "        while Q:\n",
    "            x = Q.popleft()\n",
    "            if x == n - 1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        rel = [[] for _ in range(n)]\n",
    "        for i, j in relation:\n",
    "            rel[i].append(j)\n",
    "        stack = [0]\n",
    "        for _ in range(k):\n",
    "            res = []\n",
    "            for i in stack:\n",
    "                res += rel[i]\n",
    "            stack = res\n",
    "        return stack.count(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n下标，k轮\n",
    "    def numWays(self, n: int, relation: list, k: int) -> int:\n",
    "        ways = collections.defaultdict(list)\n",
    "        for r in relation:\n",
    "            src = r[0]\n",
    "            dst = r[1]\n",
    "            ways[src].append(dst)\n",
    "        que = deque()\n",
    "        que.append(0)\n",
    "        step = 0\n",
    "        while que and step < k:\n",
    "            step += 1\n",
    "            m = len(que)\n",
    "            # 逐层进行访问，每一层相当于一步\n",
    "            for i in range(m):\n",
    "                cur = que.popleft()\n",
    "                for next in ways[cur]:\n",
    "                    que.append(next)\n",
    "        count = 0\n",
    "        # 经历k步，队列中节点能到达n-1的数量\n",
    "        if step==k:\n",
    "            while que:\n",
    "                cur = que.popleft()\n",
    "                if cur == n - 1:\n",
    "                    count += 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        edges = collections.defaultdict(list)\n",
    "        for edge in relation:\n",
    "            src = edge[0]\n",
    "            dst = edge[1]\n",
    "            edges[src].append(dst)\n",
    "        \n",
    "        steps = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue and steps<k:\n",
    "            steps += 1\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                index = queue.popleft()\n",
    "                to = edges[index]\n",
    "                #不需要考虑去重的问题，只需要一直走即可\n",
    "                for nextIndex in to:\n",
    "                    queue.append(nextIndex)\n",
    "        \n",
    "        ways = 0\n",
    "        if steps == k:\n",
    "            #遍历第k步所有可能经过的节点，如果是n-1则路径加1\n",
    "            while queue:\n",
    "                if queue.popleft() == n-1:\n",
    "                    ways += 1\n",
    "        return ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        #传递k步，传递到编号为n-1\n",
    "        edges=defaultdict(list)\n",
    "        # for i,j in edges:edges[i].append(j)#傻了呀\n",
    "        for i,j in relation:edges[i].append(j)\n",
    "        que=deque([0])#起点\n",
    "        step=0\n",
    "        while que and step<k:\n",
    "            print(que)\n",
    "            for i in range(len(que)):\n",
    "                idx=que.popleft()\n",
    "                for j in edges[idx]:\n",
    "                    que.append(j)\n",
    "                # step+=1 #不是这\n",
    "            #这一层全部走完之后，才step+1\n",
    "            step+=1\n",
    "        # print(step)\n",
    "        ways=0\n",
    "        if step==k:\n",
    "            for i in que:\n",
    "                if i==n-1:ways+=1#经过k步之后，需要走到n-1这个点，其他的不行\n",
    "        return ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "2\n",
    "[[0,1]]\n",
    "1\n",
    "\n",
    "2\n",
    "[[0,1],[1,0]]\n",
    "5\n",
    "\n",
    "2\n",
    "[[0,1],[1,0]]\n",
    "4\n",
    "\n",
    "5\n",
    "[[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]]\n",
    "3\n",
    "3\n",
    "[[0,2],[2,1]]\n",
    "2\n",
    "\n",
    "2 <= n <= 10\n",
    "1 <= k <= 5\n",
    "1 <= relation.length <= 90, 且 relation[i].length == 2\n",
    "0 <= relation[i][0],relation[i][1] < n 且\n",
    "        relation[i][0] != relation[i][1]\n",
    "\n",
    "深度优先搜索,广度优先搜索,图,动态规划\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    # TODO: detect cycle\n",
    "    # 2\n",
    "    # [[0,1],[1,0]]\n",
    "    # 4\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        table = [[] for _ in range(n)]\n",
    "        for r in relation: table[r[0]].append(r[1])\n",
    "\n",
    "        que = deque([0])\n",
    "        steps = 0\n",
    "        res = 0\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            steps += 1\n",
    "            if steps > k:\n",
    "                return res\n",
    "            while size:\n",
    "                size -= 1\n",
    "                node = que.popleft()\n",
    "                for nextNode in table[node]:\n",
    "                    if nextNode == n-1 and steps == k:\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        que.append(nextNode)\n",
    "        return res\n",
    "\n",
    "    \"\"\"\n",
    "    # DFS\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        table = [[] for _ in range(n)]\n",
    "        for r in relation:\n",
    "            table[r[0]].append(r[1])\n",
    "        res = [0]\n",
    "        self.dfs(table, 0, res, 0, k)\n",
    "        return res[0]\n",
    "    def dfs(self, table, idx, res, steps, k):\n",
    "        if idx+1 == len(table) and steps == k:\n",
    "            res[0] += 1\n",
    "            return\n",
    "        if steps >= k: return\n",
    "        for target in table[idx]:\n",
    "            self.dfs(table, target, res, steps+1, k)\n",
    "    \"\"\"\n",
    "    \"\"\"\n",
    "    # DP\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        for _ in range(k):\n",
    "            nxt = [0]*n\n",
    "            for r in relation:\n",
    "                nxt[r[1]] += dp[r[0]]\n",
    "            dp, nxt = nxt, dp\n",
    "        return dp[-1]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "2\n",
    "[[0,1]]\n",
    "1\n",
    "\n",
    "2\n",
    "[[0,1],[1,0]]\n",
    "5\n",
    "\n",
    "2\n",
    "[[0,1],[1,0]]\n",
    "4\n",
    "\n",
    "5\n",
    "[[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]]\n",
    "3\n",
    "3\n",
    "[[0,2],[2,1]]\n",
    "2\n",
    "\n",
    "2 <= n <= 10\n",
    "1 <= k <= 5\n",
    "1 <= relation.length <= 90, 且 relation[i].length == 2\n",
    "0 <= relation[i][0],relation[i][1] < n 且\n",
    "        relation[i][0] != relation[i][1]\n",
    "\n",
    "深度优先搜索,广度优先搜索,图,动态规划\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    # BFS\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        table = [[] for _ in range(n)]\n",
    "        for r in relation: table[r[0]].append(r[1])\n",
    "\n",
    "        que = deque([0])\n",
    "        steps = 0\n",
    "        res = 0\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            steps += 1\n",
    "            if steps > k: return res\n",
    "            while size:\n",
    "                size -= 1\n",
    "                node = que.popleft()\n",
    "                for nextNode in table[node]:\n",
    "                    if nextNode == n-1 and steps == k:\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        que.append(nextNode)\n",
    "        return res\n",
    "\n",
    "    \"\"\"\n",
    "    # DFS\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        table = [[] for _ in range(n)]\n",
    "        for r in relation:\n",
    "            table[r[0]].append(r[1])\n",
    "        res = [0]\n",
    "        self.dfs(table, 0, res, 0, k)\n",
    "        return res[0]\n",
    "    def dfs(self, table, idx, res, steps, k):\n",
    "        if idx+1 == len(table) and steps == k:\n",
    "            res[0] += 1\n",
    "            return\n",
    "        if steps >= k: return\n",
    "        for target in table[idx]:\n",
    "            self.dfs(table, target, res, steps+1, k)\n",
    "    \"\"\"\n",
    "    \"\"\"\n",
    "    # DP\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        for _ in range(k):\n",
    "            nxt = [0]*n\n",
    "            for r in relation:\n",
    "                nxt[r[1]] += dp[r[0]]\n",
    "            dp, nxt = nxt, dp\n",
    "        return dp[-1]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        edges = collections.defaultdict(list)\n",
    "        for edge in relation:\n",
    "            src = edge[0]\n",
    "            dst = edge[1]\n",
    "            edges[src].append(dst)\n",
    "        steps = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue and steps < k:\n",
    "            steps += 1\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                index = queue.popleft()\n",
    "                to = edges[index]\n",
    "                for nextIndex in to:\n",
    "                    queue.append(nextIndex)\n",
    "        ways = 0\n",
    "        if steps ==k:\n",
    "            while queue:\n",
    "                if queue.popleft() == n-1:\n",
    "                    ways += 1\n",
    "        return ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        adjvex = collections.defaultdict(set)\n",
    "        for x, y in relation:\n",
    "            adjvex[x].add(y)\n",
    "        \n",
    "        Q = collections.deque()\n",
    "        Q.append(0)\n",
    "        step = 0\n",
    "        while Q and step < k:\n",
    "            cur_len = len(Q)\n",
    "            for _ in range(cur_len):\n",
    "                x = Q.popleft()\n",
    "                for y in adjvex[x]:\n",
    "                    Q.append(y)\n",
    "            step += 1\n",
    "\n",
    "        res = 0\n",
    "        while Q:\n",
    "            x = Q.popleft()\n",
    "            if x == n - 1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        path=defaultdict(list)\n",
    "        for i,j in relation:\n",
    "            path[i].append(j)\n",
    "        def bfs(path,start,n,k):\n",
    "            que=[start]\n",
    "            step=0\n",
    "            res=0\n",
    "            while que and step<k:\n",
    "                step+=1\n",
    " #               print(que)\n",
    "                for i in range(len(que)):\n",
    "                    cur=que.pop(0)\n",
    "                    que+=path[cur]\n",
    "            if step==k:\n",
    "                for i in que:\n",
    "                    if i == n-1:\n",
    "                        res+=1\n",
    "            \n",
    "            return res\n",
    "        return bfs(path,0,n,k)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dp = []\n",
    "        for i in range(k + 1):\n",
    "            dp.append([])\n",
    "        dp[0] = [0]\n",
    "        for i in range(1,k + 1):\n",
    "            for j in dp[i - 1]:\n",
    "                for m in relation:\n",
    "                    if m[0] == j:\n",
    "                        dp[i].append(m[1])\n",
    "        \n",
    "        count = 0\n",
    "        for i in dp[k]:\n",
    "            if i == n - 1:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in relation:\n",
    "            g[u].append(v)\n",
    "        ans = 0\n",
    "        f = [0]\n",
    "        for _ in range(k):\n",
    "            res = []\n",
    "            for i in f:\n",
    "                res += g[i]\n",
    "                f = res\n",
    "            # print(res)\n",
    "        return res.count(n-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        result = 0\n",
    "        d = dict()\n",
    "        step = 0\n",
    "        for i in range(n):\n",
    "            d[i] = []  \n",
    "        \n",
    "        for i in range(len(relation)):\n",
    "            cur = relation[i]\n",
    "            d[cur[0]].append(cur[1])\n",
    "\n",
    "        def bfs(d, step, result):\n",
    "            queue_cur = [0]\n",
    "            queue_next = []\n",
    "            while queue_cur and step <= k:\n",
    "                cur_peo = queue_cur.pop(0)\n",
    "                if cur_peo == n-1 and step == k:\n",
    "                    result += 1\n",
    "                elif step < k and len(d[cur_peo]):\n",
    "                    for next_peo in d[cur_peo]:\n",
    "                        queue_next.append(next_peo)\n",
    "                if not queue_cur:\n",
    "                    queue_cur = queue_next\n",
    "                    queue_next = []\n",
    "                    step += 1\n",
    "            return result\n",
    "            \n",
    "\n",
    "        result = bfs(d, 0, 0)\n",
    "\n",
    "        return result\n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        d = [[] for _ in range(k + 1)]  # 可以到达的地方\n",
    "        d[0].append(0)\n",
    "        sum = 0\n",
    "        for j in range(k):\n",
    "            for p in d[j]:\n",
    "                for i in range(len(relation)):\n",
    "                    if relation[i][0]==p:\n",
    "                        d[j + 1].append(relation[i][1])\n",
    "        for i in range(len(d[k])):\n",
    "            if d[k][i] == n - 1:\n",
    "                sum += 1\n",
    "        return sum\n",
    "               \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        rec = dict()\n",
    "        for i in range(len(relation)):\n",
    "            if relation[i][0] in rec.keys():\n",
    "                rec[relation[i][0]].append(relation[i][1])\n",
    "            else:\n",
    "                rec[relation[i][0]] = [relation[i][1]]\n",
    "        cur = [0]\n",
    "        for i in range(k):\n",
    "            nex = []\n",
    "            for x in cur:\n",
    "                if x in rec.keys():\n",
    "                    nex += rec[x]\n",
    "            cur = nex \n",
    "        count = 0\n",
    "        for j in cur:\n",
    "            if j == n-1:\n",
    "                count += 1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        target_node = [0]\n",
    "        for _ in range(k):\n",
    "            new_node = []\n",
    "            for node in target_node:\n",
    "                for pair in relation:\n",
    "                    if node == pair[0]:\n",
    "                        new_node.append(pair[1])\n",
    "        \n",
    "            target_node = new_node\n",
    "\n",
    "        return target_node.count(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "\n",
    "        xuan={}\n",
    "        for a,b in relation:\n",
    "            er=xuan.get(a,set())\n",
    "            er.add(b)\n",
    "            xuan[a]=er\n",
    "\n",
    "        xia=[0]\n",
    "        for i in range(k):\n",
    "            xiayi=[]\n",
    "            for j in xia:\n",
    "                er=xuan.get(j,set())\n",
    "                for p in er:\n",
    "                    xiayi.append(p)\n",
    "\n",
    "            xia=xiayi\n",
    "\n",
    "        ans=0\n",
    "        for p in xia:\n",
    "            if p==n-1:\n",
    "                ans+=1\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        def dfs(node: int, path: List[int]) -> None:\n",
    "            # 路径加入当前节点\n",
    "            path.append(node)\n",
    "            \n",
    "            # O(V) 递归终止条件：若已经过k轮\n",
    "            if len(path) == k + 1:\n",
    "                # 若当前节点为终点，加入答案\n",
    "                if node == n-1:\n",
    "                    paths.append(path.copy())\n",
    "                    self.ans += 1 \n",
    "            else:\n",
    "                for neighbor in g[node]:\n",
    "                    dfs(neighbor, path)\n",
    "            \n",
    "            # 回溯：弹出当前节点，还原path\n",
    "            path.pop()\n",
    "\n",
    "        # 1. O(E) build adjacency list of directed graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in relation:\n",
    "            g[u].append(v)\n",
    "\n",
    "        # 2. O(V^k) traverse the graph for k levels\n",
    "        paths = []   # 所有符合条件的路径\n",
    "        self.ans = 0\n",
    "        dfs(0, [])\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "\n",
    "        # bfs\n",
    "        queue = [(0,0)] # start from 0, pass 0 time\n",
    "        rel = {}\n",
    "        for s,v in relation:\n",
    "            if s in rel.keys():\n",
    "                rel[s].append(v)\n",
    "            else:\n",
    "                rel[s] = [v]\n",
    "        # print(rel, queue)\n",
    "        ans = 0\n",
    "        step = 0\n",
    "        while queue:\n",
    "            cur, step = queue.pop()\n",
    "            # print(cur, step)\n",
    "            if cur in rel.keys():\n",
    "                for v in rel[cur]:\n",
    "                    # print(v, step)\n",
    "                    if (step==k-1) and (v==n-1):\n",
    "                        ans += 1\n",
    "                    elif (step<k):\n",
    "                        queue.insert(0,(v,step+1))\n",
    "            #print(queue)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        self.relation = relation\n",
    "        self.k = k\n",
    "        self.ans = []\n",
    "        src = 0\n",
    "        dst = n - 1\n",
    "        self.dfs(src,dst,prev=[src])\n",
    "        #print(self.ans)\n",
    "        return len(self.ans)\n",
    "    def dfs(self,src,dst,prev=[]):\n",
    "        \n",
    "        if src == dst and not prev in self.ans and len(prev) == self.k + 1:\n",
    "            #print(self.ans)\n",
    "            self.ans.append(prev)\n",
    "            return\n",
    "        if len(prev) >= self.k+1:\n",
    "            return\n",
    "        for relate in self.relation:\n",
    "            if src == relate[0]:\n",
    "                self.dfs(relate[1],dst,prev+[relate[1]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        path_tree = [[] for _ in range(n)]\n",
    "        cur_stage = 0\n",
    "        res = 0\n",
    "        for left, right in relation:\n",
    "            path_tree[left].append(right)\n",
    "        print(path_tree)\n",
    "        path_deque = deque([[0]])\n",
    "        while len(path_deque) and cur_stage <= k:\n",
    "            cur_nodes = path_deque.popleft()\n",
    "            next_nodes = []\n",
    "            for cur_node in cur_nodes:\n",
    "                if cur_stage == k:\n",
    "                    if cur_node == n - 1:\n",
    "                        res += 1\n",
    "                else:\n",
    "                    next_nodes.extend(path_tree[cur_node])\n",
    "            if next_nodes:\n",
    "                path_deque.append(next_nodes)\n",
    "            cur_stage += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        self.temp = {}\n",
    "        for i in range(n):\n",
    "            self.temp[i] = []\n",
    "        for li in relation:\n",
    "            self.temp[li[1]].append(li[0])\n",
    "        ret = self.cal(k-1, self.temp[n-1])\n",
    "        return ret\n",
    "    \n",
    "    def cal(self, k, array):\n",
    "        tmp = []\n",
    "        print(array)\n",
    "        if k == 0:\n",
    "            ret = 0\n",
    "            for i in array:\n",
    "                if i == 0:\n",
    "                    ret += 1\n",
    "            return ret\n",
    "        for i in array:\n",
    "            tmp += self.temp[i]\n",
    "        return self.cal(k-1, tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def backtrack(self, node, target, graph, path, k, res):\n",
    "      if len(path) == k:\n",
    "        if node == target:\n",
    "          res.append(path.copy())\n",
    "        return\n",
    "      for nxt in graph[node]:\n",
    "        path.append(nxt)\n",
    "        self.backtrack(nxt, target, graph, path, k, res)\n",
    "        path.pop()\n",
    "      \n",
    "\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "      graph = defaultdict(set)\n",
    "      for s, d in relation:\n",
    "        graph[s].add(d)\n",
    "      path = [0]\n",
    "      res = []\n",
    "      self.backtrack(0, n-1, graph, path, k + 1, res)\n",
    "      return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        #定义数组，每个位置表示从这个位置可以传递给的位置有\n",
    "        a=[[] for i in range(n)]\n",
    "        for i in relation:\n",
    "            a[i[0]].append(i[1])\n",
    "        print(a)\n",
    "        #用来记录上一次的终点\n",
    "        b=[n-1]\n",
    "        #用来记录下一次的起点\n",
    "        c=[]\n",
    "        while(k>0):\n",
    "            #对与上一次传递的终点，我们推出他的前一次的起点是什么\n",
    "            for j in b:\n",
    "                for i in range(len(a)):\n",
    "                    if j in a[i]:\n",
    "                        c.append(i)\n",
    "            print(k,c)\n",
    "            k-=1\n",
    "            if k==0:\n",
    "                return c.count(0)\n",
    "            b=c\n",
    "            c=[]\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        adjvex = defaultdict(list)\n",
    "        for x, y in relation:\n",
    "            adjvex[x].append(y)\n",
    "\n",
    "        Q = [0]\n",
    "        step = 0\n",
    "        while Q and step < k:\n",
    "            for _ in range(len(Q)):\n",
    "                for y in adjvex[Q.pop(0)]:\n",
    "                    Q.append(y)\n",
    "            step += 1\n",
    "        print(Q)\n",
    "        return Q.count(n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        relations = collections.defaultdict(list)\n",
    "        for player1, player2 in relation:\n",
    "            relations[player1].append(player2)\n",
    "        players = [0]\n",
    "        print(relations)\n",
    "        while k > 0:\n",
    "            nex = []\n",
    "            print(players)\n",
    "            for player in players:\n",
    "                nex.extend(relations[player])\n",
    "            print(':',nex)\n",
    "            players = nex\n",
    "            \n",
    "            k -= 1\n",
    "        return players.count(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        point=[0]\n",
    "        ans=0\n",
    "        for i in range(1,k+1):\n",
    "            point=self.bfs(point,relation)\n",
    "            print(point)\n",
    "        for i in point:\n",
    "            if i ==n-1:\n",
    "                 ans+=1\n",
    "        return ans \n",
    "  \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def bfs(self,points,relations):\n",
    "        \n",
    "        next_point=[]\n",
    "\n",
    "        for point in points:\n",
    "            next_point+= [rela[1] for rela in relations if rela[0]==point]\n",
    "        \n",
    "        return next_point\n",
    "        \n",
    "\n",
    "     \n",
    "        \n",
    "      \n",
    "        \n",
    "        if len(next_point)==0:\n",
    "            return \n",
    "        dp[start]=step+1\n",
    "        for point in points:\n",
    "            self.bfs(point,end,relations,dp,step)\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        # 深度优先搜索\n",
    "        g = {i:[] for i in range(n)}\n",
    "        for (v1, v2) in relation:\n",
    "            g[v1].append(v2)\n",
    "        roads = []\n",
    "        def search(cur, dest, road):\n",
    "            road.append(cur)\n",
    "            if cur == dest and len(road) == k+1:\n",
    "                roads.append(road)\n",
    "                return\n",
    "            if len(road) >= k+1:\n",
    "                return\n",
    "            neigbors = g[cur]\n",
    "            for n in neigbors:\n",
    "                search(n, dest, road[:])\n",
    "\n",
    "        search(0, n-1, [])\n",
    "        return len(roads)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # result = 0\n",
    "\n",
    "        # g = {}\n",
    "        # for (v1, v2) in relation:\n",
    "        #     if v1 not in g:\n",
    "        #         g[v1] = []\n",
    "        #     if v2 not in g:\n",
    "        #         g[v2] = []\n",
    "        #     g[v1].append(v2)\n",
    "\n",
    "        # start = 0\n",
    "        # dest = n - 1\n",
    "        # roads = []\n",
    "        # def search(cur, dest, g, road):\n",
    "        #     road.append(cur)\n",
    "        #     if len(road) == k+1 and cur == dest:\n",
    "        #         roads.append(road)\n",
    "        #         return\n",
    "        #     elif len(road) > k:\n",
    "        #         return\n",
    "            \n",
    "        #     neigbors = g[cur]\n",
    "        #     for n in neigbors:\n",
    "        #         search(n, dest, g, road[:])\n",
    "\n",
    "        # search(start, dest, g, [])\n",
    "        # return len(roads)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        q = collections.deque()\n",
    "        for cell in relation:\n",
    "            graph[cell[0]].append(cell[1])\n",
    "        q.append(0)\n",
    "        res = 0\n",
    "        while q and k+1:\n",
    "            k -= 1\n",
    "            print(q,k)\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node == n-1 and k == -1:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    for a in graph[node]:\n",
    "                        q.append(a)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        G = collections.defaultdict(list)\n",
    "        for u, v in relation:\n",
    "            G[u].append(v)\n",
    "        que = collections.deque([(0, 0)])\n",
    "        res = 0\n",
    "        while que:\n",
    "            u, rnd = que.popleft()\n",
    "            if rnd == k:\n",
    "                res += u == n - 1\n",
    "            if rnd < k and u in G:\n",
    "                for v in G[u]:\n",
    "                    que.append((v, rnd + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        #深度优先搜索\n",
    "        g = {i:[] for i in range(n)}\n",
    "        for(v1, v2) in relation:\n",
    "            g[v1].append(v2)\n",
    "\n",
    "        roads = []\n",
    "        def search(cur, dest, road):\n",
    "            road.append(cur)\n",
    "            if cur == dest and len(road) == k+1:\n",
    "                roads.append(road)\n",
    "                return\n",
    "            if len(road) >= k+1:\n",
    "                return\n",
    "            neigbors = g[cur]\n",
    "            for n in neigbors:\n",
    "                search(n, dest, road[:])\n",
    "\n",
    "        search(0, n-1, [])\n",
    "        return len(roads)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        allPaths = []\n",
    "        edges = [[] for i in range(n)]\n",
    "        for li in relation:\n",
    "            edges[li[0]].append(li[1])\n",
    "        # print(edges)\n",
    "        stack = []\n",
    "        steps = -1\n",
    "\n",
    "        def dfs(start, steps):\n",
    "            # print(stack, steps, allPaths)\n",
    "            # if not start:\n",
    "            #     return\n",
    "            steps += 1\n",
    "            stack.append(start)\n",
    "            if steps == k and start == n-1:\n",
    "                allPaths.append([stack[:]])\n",
    "            elif steps < k:\n",
    "                for x in edges[start]:\n",
    "                    # print(\"next point:\", x)\n",
    "                    dfs(x, steps)\n",
    "            elif steps > k:\n",
    "                return\n",
    "            stack.pop()\n",
    "\n",
    "        dfs(0, steps)\n",
    "        return len(allPaths)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        # 深度优先搜索\n",
    "        g = {i:[] for i in range(n)}\n",
    "        for (v1, v2) in relation:\n",
    "            g[v1].append(v2)\n",
    "\n",
    "            \n",
    "        roads = []\n",
    "        def search(cur, dest, road):\n",
    "            road.append(cur)\n",
    "            if cur == dest and len(road) == k+1:\n",
    "                roads.append(road)\n",
    "                return\n",
    "            if len(road) >= k+1:\n",
    "                return\n",
    "            neigbors = g[cur]\n",
    "            for n in neigbors:\n",
    "                search(n, dest, road[:])\n",
    "\n",
    "        search(0, n-1, [])\n",
    "        return len(roads)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # result = 0\n",
    "\n",
    "        # g = {}\n",
    "        # for (v1, v2) in relation:\n",
    "        #     if v1 not in g:\n",
    "        #         g[v1] = []\n",
    "        #     if v2 not in g:\n",
    "        #         g[v2] = []\n",
    "        #     g[v1].append(v2)\n",
    "\n",
    "        # start = 0\n",
    "        # dest = n - 1\n",
    "        # roads = []\n",
    "        # def search(cur, dest, g, road):\n",
    "        #     road.append(cur)\n",
    "        #     if len(road) == k+1 and cur == dest:\n",
    "        #         roads.append(road)\n",
    "        #         return\n",
    "        #     elif len(road) > k:\n",
    "        #         return\n",
    "            \n",
    "        #     neigbors = g[cur]\n",
    "        #     for n in neigbors:\n",
    "        #         search(n, dest, g, road[:])\n",
    "\n",
    "        # search(start, dest, g, [])\n",
    "        # return len(roads)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, Counter\n",
    "from copy import deepcopy\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        relations = defaultdict(list)\n",
    "        for f,t in relation:\n",
    "            relations[f].append(t)\n",
    "        # print(relations)\n",
    "\n",
    "        count = 0\n",
    "        queue = deepcopy(relations[0])\n",
    "        k -= 1\n",
    "        while queue and k > 0:\n",
    "            len_ = len(queue)\n",
    "            for i in range(len_):\n",
    "                cur = queue.pop(0)\n",
    "                tmp = relations[cur]\n",
    "                queue = queue + tmp\n",
    "            # print(queue, k)\n",
    "            k -= 1 \n",
    "\n",
    "        c = Counter(queue)\n",
    "        return c[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        queue = collections.deque()\n",
    "        queue.append(0)\n",
    "        step = 0\n",
    "        res = 0\n",
    "        while queue and step <= k:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if cur == n - 1 and step == k:\n",
    "                    res += 1\n",
    "                for rel in relation:\n",
    "                    if rel[0] != cur:\n",
    "                        continue\n",
    "                    nxt = rel[1]\n",
    "                    queue.append(nxt)\n",
    "            step += 1\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import  defaultdict\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        for f,t in relation:\n",
    "            dic[t].append(f)\n",
    "        \n",
    "        s=[n-1]\n",
    "        for i in range(k):\n",
    "            temp=list()\n",
    "            for x in s:\n",
    "                if x in dic.keys():\n",
    "                    temp+=dic[x]\n",
    "            s=temp[:]\n",
    "        return s.count(0)\n",
    "        \n",
    "        # return dic.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        data_dict = {}\n",
    "        for one in relation:\n",
    "            if one[0] in data_dict:\n",
    "                data_dict[one[0]].add(one[1])\n",
    "            else:\n",
    "                data_dict[one[0]] = set([one[1]])\n",
    "        queue, cnt = [], 0\n",
    "        if 0 not in data_dict:\n",
    "            return 0\n",
    "        \n",
    "        for ele in data_dict[0]:\n",
    "            queue.append((ele, 1))\n",
    "        while queue:\n",
    "            top = queue.pop(0)\n",
    "            if top[1] == k and top[0] == n-1:\n",
    "                cnt += 1\n",
    "            if top[1] < k and top[0] in data_dict:\n",
    "                for ele in data_dict[top[0]]:\n",
    "                    queue.append((ele, top[1]+1))\n",
    "        return cnt\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        a=relation\n",
    "        x=0\n",
    "        b=[[] for i in range(n)]\n",
    "        for i in range(len(a)):\n",
    "            b[a[i][0]].append(a[i][1])\n",
    "            tar=b[0]\n",
    "        for  u in range(k-1):\n",
    "            r=[]\n",
    "            for i in range(len(tar)):\n",
    "                r=r+b[tar[i]]\n",
    "            tar=r\n",
    "        s=0\n",
    "        for i in range(len(tar)):\n",
    "            if tar[i]==n-1:\n",
    "                s=s+1\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        queue = collections.deque()\n",
    "        visited = set()\n",
    "        queue.append(0)\n",
    "        visited.add(0)\n",
    "        step = 0\n",
    "        res = 0\n",
    "        while queue and step <= k:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if cur == n - 1 and step == k:\n",
    "                    res += 1\n",
    "                for rel in relation:\n",
    "                    if rel[0] != cur:\n",
    "                        continue\n",
    "                    nxt = rel[1]\n",
    "                    queue.append(nxt)\n",
    "                    visited.add(nxt)\n",
    "            step += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        pass_dict = defaultdict(list)\n",
    "        for pair in relation:\n",
    "            pass_dict[pair[0]].append(pair[1])\n",
    "\n",
    "        kids_holding_message = [0]\n",
    "        for round_number in range(k):\n",
    "            kids_holding_message = [pass_dict[kid] for kid in kids_holding_message]\n",
    "            kids_holding_message = sum(kids_holding_message, [])\n",
    "\n",
    "        return kids_holding_message.count(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "\n",
    "        edge_dict = {}\n",
    "        for _from, _to in relation:\n",
    "            if _to in edge_dict:\n",
    "                edge_dict[_to].append(_from)\n",
    "            else:\n",
    "                edge_dict[_to] = []\n",
    "                edge_dict[_to].append(_from)\n",
    "        stack = [n - 1]\n",
    "        count = 0\n",
    "        while stack and count < k:\n",
    "            next_layer = []\n",
    "            while stack:\n",
    "                cur = stack.pop()\n",
    "                next_layer = next_layer + edge_dict.get(cur, [])\n",
    "            stack = next_layer\n",
    "            count = count + 1\n",
    "        return len([i for i in stack if i == 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        Hash = collections.defaultdict(list)\n",
    "        deq = deque([])\n",
    "        for i in range(len(relation)):\n",
    "            if relation[i][0] == 0:\n",
    "                deq.append((relation[i]))\n",
    "            Hash[relation[i][0]].append(relation[i][1])\n",
    "        ans = 0\n",
    "        level = 0\n",
    "        while deq:\n",
    "            # print(deq)\n",
    "            length = len(deq)\n",
    "            level += 1\n",
    "            if level > k:\n",
    "                break\n",
    "            # print(deq, level)\n",
    "            for i in range(length):\n",
    "                start, end = deq.pop()\n",
    "                if level == k:\n",
    "                    ans += 1 if end == n - 1 else 0\n",
    "                    continue\n",
    "                for num in Hash[end]:\n",
    "                    deq.appendleft((end, num))\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        m = len(relation)\n",
    "        queue = [(0,0)]\n",
    "        path = [(0,0)]\n",
    "        # visited = [0]\n",
    "        while queue:\n",
    "            idx, depth = queue.pop(0)\n",
    "            if depth == k:\n",
    "                if idx == n-1:\n",
    "                    res += 1 \n",
    "                continue\n",
    "            for i,v in enumerate(relation):\n",
    "                if v[0] == idx:\n",
    "                    queue.append((v[1], depth + 1))\n",
    "        return res\n",
    "            \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        temp=1\n",
    "        count=0\n",
    "        j=[(0,1)]\n",
    "        while temp:\n",
    "            now,now_c=j.pop(0)\n",
    "            temp-=1\n",
    "            for i in relation:\n",
    "                if i[0]==now:    \n",
    "                    j.append((i[1],now_c+1))\n",
    "                    if now_c<k:\n",
    "                        temp+=1\n",
    "        for i in j:\n",
    "            if i[0]==n-1:\n",
    "                count+=1 \n",
    "        return count \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        count=0\n",
    "        queue=[(0,0)]\n",
    "        while len(queue)>0:\n",
    "            boy,path=queue.pop(0)\n",
    "            if path==k and boy==n-1:\n",
    "                count+=1\n",
    "\n",
    "            for x in relation:\n",
    "                if boy==x[0] and path<k:\n",
    "                    queue.append((x[1],path+1))\n",
    "                    \n",
    "        return count\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        # res = 0\n",
    "        #\n",
    "        # def dfs(tmp, k):\n",
    "        #     nonlocal res\n",
    "        #     if k == 0:\n",
    "        #         if tmp[-1] == n - 1:\n",
    "        #             res += 1\n",
    "        #         return\n",
    "        #     for a, b in relation:\n",
    "        #         if tmp[-1] == a:\n",
    "        #             dfs([a, b], k - 1)\n",
    "        #\n",
    "        # dfs(relation[0], k-1)\n",
    "        # return res\n",
    "\n",
    "        \"\"\"dfs2\"\"\"\n",
    "        res = []\n",
    "\n",
    "        def dfs(tmp):\n",
    "            if len(tmp) == k:\n",
    "                if tmp[-1][-1] == n - 1:\n",
    "                    res.append(tmp[:])\n",
    "                return\n",
    "            elif len(tmp) < k + 1:\n",
    "                for a, b in relation:\n",
    "                    if tmp[-1][1] == a:\n",
    "                        dfs(tmp + [[a, b]])\n",
    "\n",
    "        for a, b in relation:\n",
    "            if a == 0:\n",
    "                dfs([[a, b]])\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        q = [(0, 0)]\n",
    "        for i in range(k):\n",
    "            while(q and q[0][1] == i):\n",
    "                p = q.pop(0)\n",
    "                for r in relation:\n",
    "                    if r[0] == p[0]:\n",
    "                        q.append((r[1], i+1))\n",
    "        return len([ 1 for item in q if item[0] == n-1])\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        relation_map = dict()\n",
    "        for i in range(0, len(relation)):\n",
    "            start = relation[i][0]\n",
    "            if start not in relation_map:\n",
    "                relation_map[start] = []\n",
    "            relation_map[start].append(relation[i][1])\n",
    "\n",
    "        if 0 not in relation_map:\n",
    "            return 0\n",
    "        cases_num = 0\n",
    "        op_queue = [[0, ]]\n",
    "        while op_queue:\n",
    "            case = op_queue[0]\n",
    "            if len(case) == k + 1:\n",
    "                if case[-1] == n - 1:\n",
    "                    cases_num += 1\n",
    "                op_queue.pop(0)\n",
    "                continue\n",
    "            if case[-1] not in relation_map:\n",
    "                op_queue.pop(0)\n",
    "                continue\n",
    "\n",
    "            nexts = relation_map[case[-1]]\n",
    "            if nexts:\n",
    "                if len(nexts) > 1:\n",
    "                    for ne in nexts[1:]:\n",
    "                        op_queue.append(case + [ne, ])\n",
    "                case.append(nexts[0])\n",
    "        return cases_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        queue=[(k,0)]\n",
    "        while k:\n",
    "            if not queue:\n",
    "                return 0\n",
    "            else:\n",
    "                beg=queue.pop(0)\n",
    "                for i in range(len(relation)):\n",
    "                    if relation[i][0]==beg[1]:\n",
    "                        queue.append((k-1,relation[i][1]))\n",
    "                k=queue[0][0]\n",
    "                                  \n",
    "        count=0\n",
    "        while queue:\n",
    "            t=queue.pop(0)\n",
    "            if t[1]==n-1:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        relation_map = dict()\n",
    "        for i in range(0, len(relation)):\n",
    "            start = relation[i][0]\n",
    "            if start not in relation_map:\n",
    "                relation_map[start] = []\n",
    "            relation_map[start].append(relation[i][1])\n",
    "\n",
    "        if 0 not in relation_map:\n",
    "            return 0\n",
    "        cases_num = 0\n",
    "        op_queue = [[0, ]]\n",
    "        while op_queue:\n",
    "            case = op_queue[0]\n",
    "            if len(case) == k + 1:\n",
    "                if case[-1] == n - 1:\n",
    "                    cases_num += 1\n",
    "                op_queue.pop(0)\n",
    "                continue\n",
    "            if case[-1] not in relation_map:\n",
    "                op_queue.pop(0)\n",
    "                continue\n",
    "\n",
    "            nexts = relation_map[case[-1]]\n",
    "            if nexts:\n",
    "                if len(nexts) > 1:\n",
    "                    for ne in nexts[1:]:\n",
    "                        op_queue.append(case + [ne, ])\n",
    "                case.append(nexts[0])\n",
    "        return cases_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "        relation_map = dict()\n",
    "        for i in range(0, len(relation)):\n",
    "            start = relation[i][0]\n",
    "            if start not in relation_map:\n",
    "                relation_map[start] = []\n",
    "            relation_map[start].append(relation[i][1])\n",
    "\n",
    "        if 0 not in relation_map:\n",
    "            return 0\n",
    "        cases_num = 0\n",
    "        op_queue = [[0, ]]\n",
    "        while op_queue:\n",
    "            case = op_queue[0]\n",
    "            if len(case) == k + 1:\n",
    "                if case[-1] == n - 1:\n",
    "                    cases_num += 1\n",
    "                op_queue.pop(0)\n",
    "                continue\n",
    "            if case[-1] not in relation_map:\n",
    "                op_queue.pop(0)\n",
    "                continue\n",
    "\n",
    "            nexts = relation_map[case[-1]]\n",
    "            if nexts:\n",
    "                if len(nexts) > 1:\n",
    "                    for ne in nexts[1:]:\n",
    "                        op_queue.append(case + [ne, ])\n",
    "                case.append(nexts[0])\n",
    "        return cases_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:\n",
    "            target = n - 1\n",
    "            tempbegin = [[0]]\n",
    "            tempend = []\n",
    "            fin = 0\n",
    "            while k>0 :\n",
    "                for value in relation:\n",
    "                    for re in tempbegin:\n",
    "                        re_c = re.copy()\n",
    "                        if value[0] == re_c[-1] and k>1:\n",
    "                            re_c.append(value[1])\n",
    "                            tempend.append(re_c)\n",
    "                        elif value[0] == re_c[-1] and value[1] == target and k==1 :\n",
    "                            re_c.append(value[1])\n",
    "                            tempend.append(re_c)\n",
    "                tempbegin.clear()\n",
    "                tempbegin = tempbegin+tempend\n",
    "                tempend.clear()\n",
    "                k=k-1\n",
    "            fin = len(tempbegin)\n",
    "            return fin\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
